import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * User:xieChao
 * Date:2022/10/14 19:58
 */
public class TestSort {
    /**
     * 直接插入排序
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * 稳定性：稳定的
     * @param array
     */
    public static void inserSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            for(j = i-1;j >= 0;j--){
                if(array[j] > tmp){
                    array[j+1] = array[j];//j下标的值只要比tmp大，array[j+1] = array[j]
                }else{
                    //array[j+1] = tmp;
                    break;
                }
            }
            //j回退到小于0的地方
            array[j+1] = tmp;
        }
    }


    public static void main(String[] args) {
       int[] array = {13,2,4,23,7,9};
       inserSort(array);
        System.out.println(Arrays.toString(array));
    }
}
